package algorithms.sort;

import java.util.Stack;

/**
 * 非递归实现的快速排序
 *
 */
public class QuickSort2 {

	public static void sortNoRecrut(int[] a){
		if(a == null || a.length < 0)	return;
		Stack<Integer> lowStack = new Stack<>();
		Stack<Integer> higStack = new Stack<>();
		
		int j   = 0;
		int lo  = 0;
		int hi  = a.length -1;
		
		lowStack.push(lo);
		higStack.push(hi);
		
		while(!lowStack.isEmpty()){
			lo = lowStack.pop();
			hi = higStack.pop();
			j = partition2(a, lo, hi);
			if(lo < j - 1){
				lowStack.push(lo);
				higStack.push(j - 1);
			}
			if(hi > j + 1){
				lowStack.push(j + 1);
				higStack.push(hi);
			}
		}
	}
	
	public static void show(int[] a){
		for(int m : a)
			System.out.print(m + " ");
	}
	
	private static int partition2(int[] a, int lo, int hi){
		int i = lo, j = hi + 1;
		int left = a[lo];
		while(true){
			while(a[++i] < left) {
                if (i == hi) break;
            }
			while(a[--j] > left) {
                if (j == lo) break;
            }
			if(i >= j) break;
			exch(a, i, j);
		}
		exch(a, lo, j);
		return j;
	}

	private static void exch(int[] a, int i, int j){
		int tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}
	
	
	public static void main(String[] args) {
		int a[]={10,1,4,7,8,6,3,4,4,4,4,4,2,5,9,4,2};
//		int[] a = {3, 2, 1};
		QuickSort2.sortNoRecrut(a);
		QuickSort2.show(a);
	}

}
